package com.lecture.java8.graph;

import com.google.common.graph.GraphBuilder;
import com.google.common.graph.MutableGraph;

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 图数据结构相关的方法
 * @author luyn
 * @date 2024/11/28
 */
public class GraphUtil {


    public static MutableGraph<Long> generateMutableGraph(List<? extends NodeInfo> nodeInfoList,List<NodeLink> nodeLinkList,boolean dottedLineExclusive) {
        if (nodeInfoList == null || nodeInfoList.isEmpty()) {
            return null;
        }
        //构建有向图
        MutableGraph<Long> graph = GraphBuilder.directed().build();
        //向图中加入顶点
        for (NodeInfo nodeInfo : nodeInfoList) {
            graph.addNode(nodeInfo.getId());
        }
        //向图中加入顶点的连线
        for (NodeLink nodeLink : nodeLinkList) {
            //是否排除虚线
            if (nodeLink.isSolid() && dottedLineExclusive) {
                graph.putEdge(nodeLink.getEnterId(),nodeLink.getLeaveId());
            }
            if (!dottedLineExclusive) {
                //不需要排除虚线
                graph.putEdge(nodeLink.getEnterId(),nodeLink.getLeaveId());
            }
        }
        return graph;
    }

    public static Queue<NodeInfo> dfs(List<NodeInfo> nodeInfoList,List<NodeLink> nodeLinkList) {
        Queue<NodeInfo> queue = new LinkedBlockingQueue<>();
        Map<Long, NodeInfo> nodeMap = parseMatlabNodeMap(nodeInfoList);
        MutableGraph<Long> graph = generateMutableGraph(nodeInfoList, nodeLinkList, true);
        //是否存在入度为0的节点
        boolean hasZeroInDegree = true;
        //没有入度为0的节点时停止循环
        while (hasZeroInDegree && graph.nodes() != null && !graph.nodes().isEmpty()) {
            //重新判断是否包含入度为0的节点
            hasZeroInDegree = false;
            Long zeroInDegreeNode = null;
            for (Long node : graph.nodes()) {
                if (graph.inDegree(node) == 0) {
                    hasZeroInDegree = true;
                    zeroInDegreeNode = node;
                    break;
                }
            }
            if (hasZeroInDegree) {
                //执行入度为0的节点
                //将入度为0的节点放入队列中
                queue.offer(nodeMap.get(zeroInDegreeNode));
                //将入度为0的节点和当前节点相关的边删除
                Set<Long> successors = graph.successors(zeroInDegreeNode);
                graph.removeNode(zeroInDegreeNode);
                for (Long successor : successors) {
                    graph.removeEdge(zeroInDegreeNode,successor);
                }
            }
        }
        return queue;
    }

    public static Map<Long,NodeInfo> parseMatlabNodeMap(List<NodeInfo> nodeInfoList) {
        Map<Long,NodeInfo> nodeMap = new HashMap<>();
        for (NodeInfo nodeInfo : nodeInfoList) {
            nodeMap.put(nodeInfo.getId(),nodeInfo);
        }
        return nodeMap;
    }

    /**
     * 判断图结构是否存在环路
     * @param graph 图结构
     * @return boolean
     */
    public static <T> boolean hasLoop(MutableGraph<T> graph) {
        //
        boolean hasZeroInDegree = true;
        while (hasZeroInDegree && graph.nodes() != null && !graph.nodes().isEmpty()) {
            hasZeroInDegree = false;
            T zeroInDegreeNode = null;
            for (T node : graph.nodes()) {
                if (graph.inDegree(node) == 0) {
                    hasZeroInDegree = true;
                    zeroInDegreeNode = node;
                    break;
                }
            }
            if (hasZeroInDegree) {
                Set<T> successors = graph.successors(zeroInDegreeNode);
                graph.removeNode(zeroInDegreeNode);
                for (T successor : successors) {
                    graph.removeEdge(zeroInDegreeNode,successor);
                }
            }
        }

        if (graph.nodes() == null  || graph.nodes().isEmpty()) {
            System.out.println("图中不包含环路");
            return false;
        } else {
            System.out.println("图中包含环路");
            return true;
        }


    }

    public static void main(String[] args) {
        NodeInfo a = new NodeInfo();
        a.setId(1L);
        a.setName("A");
        NodeInfo b = new NodeInfo();
        b.setId(2L);
        b.setName("B");
        NodeInfo c = new NodeInfo();
        c.setId(3L);
        c.setName("C");
        NodeInfo d = new NodeInfo();
        d.setId(4L);
        d.setName("D");

        NodeLink ab = new NodeLink();
        ab.setEnterId(a.getId());
        ab.setLeaveId(b.getId());

        NodeLink ac = new NodeLink();
        ac.setEnterId(a.getId());
        ac.setLeaveId(c.getId());

        NodeLink bd = new NodeLink();
        bd.setEnterId(b.getId());
        bd.setLeaveId(d.getId());

        NodeLink cd = new NodeLink();
        cd.setEnterId(c.getId());
        cd.setLeaveId(d.getId());

        NodeLink da = new NodeLink();
        da.setEnterId(d.getId());
        da.setLeaveId(a.getId());

        List<NodeInfo> nodeInfoList = new ArrayList<>();
        nodeInfoList.add(a);
        nodeInfoList.add(b);
        nodeInfoList.add(c);
        nodeInfoList.add(d);

        List<NodeLink> nodeLinkList = new ArrayList<>();
        nodeLinkList.add(ab);
        nodeLinkList.add(ac);
        nodeLinkList.add(bd);
        nodeLinkList.add(cd);
        nodeLinkList.add(da);

        /*Queue<NodeInfo> queue = dfs(nodeInfoList, nodeLinkList);
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }*/

        MutableGraph<Long> graph = generateMutableGraph(nodeInfoList, nodeLinkList, true);
        System.out.println(hasLoop(graph));
    }
}
